/*
 * @lc app=leetcode.cn id=787 lang=java
 *
 * [787] K 站中转内最便宜的航班
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
// @lc code=start
class Solution {

    HashMap<Integer, List<int[]>> indegree;
    int src, dst;
    int[][] memo;   // 记忆化搜索---备忘录


    
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        this.src = src;
        this.dst = dst;
        // 将中转站的个数转化为边的个数
        k++;

        memo = new int[n][k + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -888);
        }

        indegree = new HashMap<>();
        for(int[] f : flights) {
            int from = f[0];
            int to = f[1];
            int cost = f[2];
            // 记录谁指向该节点，以及权重
            indegree.putIfAbsent(to, new LinkedList<>());
            indegree.get(to).add(new int[]{from, cost});
        }

        return dp(dst, k);

    }

    private int dp(int s, int k) {
        if(s == src) {
            return 0;
        }

        if(k == 0) {
            return -1;
        }

        // 查备忘录，防止冗余计算
        if (memo[s][k] != -888) {
            return memo[s][k];
        }

        int res = Integer.MAX_VALUE;

        if(indegree.containsKey(s)) {
            for(int[] v : indegree.get(s)) {
                int from = v[0];
                int cost = v[1];

                int subProblem = dp(from, k - 1);

                if(subProblem != -1) {
                    res = Math.min(res, subProblem + cost);
                }
            }
        }
        // 存入备忘录
        memo[s][k] = (res == Integer.MAX_VALUE) ? -1 : res;
        
        return memo[s][k];
    }
}
// @lc code=end

